package q464_canIWin;

import java.util.HashMap;
import java.util.Map;

public class Solution_2 {
    Map<Integer, Boolean> memo = new HashMap();
    boolean[] vis;

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        //最大的可以选的数(maxChoosableInteger)大于等于最终目标数(desiredTotal),A先抽，直接拿desiredTotal，胜出
        if (desiredTotal <= maxChoosableInteger) return true;
        //[1...maxChoosableInteger]之间的总数的和小于最终目标数(desiredTotal),A和By将数选完，也不能凑成(desiredTotal),A赢不了，返回false
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
        vis = new boolean[maxChoosableInteger + 1];
        return helper(desiredTotal);
    }

    public boolean helper(int desiredTotal) {
        if (desiredTotal <= 0) return false;
        int key = format(vis);
        if (!memo.containsKey(key)) {
            //遍历vis中的数，尝试没有被选中的
            for (int i = 1; i < vis.length; i++) {
                if (!vis[i]) {//i没有被选择
                    vis[i] = true;//标记
                    // 当前i被选中，留给对手的desiredTotal - i的空间，但是对手没法胜出
                    if (!helper(desiredTotal - i)) {
                        memo.put(key, true);
                        vis[i] = false;//恢复
                        return true;
                    }
                    vis[i] = false;//恢复
                }
            }
            memo.put(key, false);
        }
        return memo.get(key);
    }

    // 遍历vis数组，每一位true的设置为1，相当于压缩
    public int format(boolean[] vis) {
        int res = 0;
        for (boolean b : vis) {
            res <<= 1;
            if (b) res |= 1;
        }
        return res;
    }

}
